
#include <iostream>
#include <vector>
#include <string>
#include <assert.h>
#include <map>
#include <set>

using namespace std;

#include "AVLTree.h"
#include "RBTree.h"

void test1()
{
    AVLTree<string, string> a1;
    a1.insert(pair<string, string>("a", "我是a"));
    a1.insert(pair<string, string>("b", "我是b"));
    a1.insert(pair<string, string>("c", "我是c"));
    a1.insert(pair<string, string>("d", "我是d"));
    a1.insert(pair<string, string>("e", "我是e"));
    a1.insert(pair<string, string>("f", "我是f"));

    a1.InOrder();
}

void test2()
{
    vector<int> arr = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
    AVLTree<int, int> a;
    for (auto& e : arr)
    {
        a.insert(make_pair(e, e));
    }
    a.InOrder();
}

void test3()
{
    srand(time(0));
    int N = 1000;
    AVLTree<int, int> a;
    for (int i = 0; i < N; i++)
    {
        int x = rand();
        
        cout << "插入：" << x << ':' << i << endl;
        a.insert(make_pair(x, x));
        cout << "IsBalance : " << a.AVLTreeTrue() << endl;
    }
    a.InOrder();
}

void TestRBTree1()
{
	// 测试双旋平衡因子调节
	//int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 0,5,30,25,20,4,13,30,28,27 };  
	int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	RBTree<int, int> t1;
	for (auto e : a)
	{
		t1.insert(make_pair(e, e));
	}

	t1.InOrder();
	cout << "IsBalance:" << t1.isRBTree() << endl;
}

void TestRBTree2()
{
	size_t N = 100000;
	srand(time(0));
	RBTree<int, int> t1;
	for (size_t i = 0; i < N; ++i)
	{
		int x = rand();
		cout << "Insert:" << x << ":" << i << endl;
		t1.insert(make_pair(x, i));
		cout << "IsBalance:" << t1.isRBTree() << endl;
	}
	t1.InOrder();
	cout << "IsBalance:" << t1.isRBTree() << endl;
}

int main()
{
    //test1();
    //test2();
    //test3();

    TestRBTree1();
    TestRBTree2();

    return 0;
}
